//
// IDAStar
//

//import jade.content.onto.basic.Action;

import java.util.ArrayList;
import java.util.HashMap;

public class SearchIDAStar implements Search {

	//StateCost stores just boolean and limit together
	protected Heuristic heuristic = new RushHourHeuristic3();//hardcoded now, but should be dynamic
	protected State state;
	protected ArrayList<Long> stateSequence = new ArrayList<Long>();

	public class DFS_CRetval {
		public boolean found;
		public int limit;
		public DFS_CRetval() {
			this(false, 0);
		}
		public DFS_CRetval(boolean found, int limit) {
			this.found = found;
			this.limit = limit;
		}
	}
	
	// Input: start state
	// Output: cost of solution and the solution path.
	// Returns: true if solution found, otherwise false.
	public boolean run( State s, Cost cost, ArrayList<Action> solution ) {
		/* 
		Psedudocode from lecture notes:	
			IDA*( State start ) { 
				found = false; 
				limit = h( start ); 
				while ( !found ) { 
					<found, limit> = DFS_C( start, 0, limit ); 
				} 
				return limit; 
			} 			
		*/

		stateSequence.clear();
		m_nodesExpanded = 0;
		heuristic.init(s);    	
		state = s;
    	long initialStateId = s.getStateID();
    	int limit = heuristic.getHeuristic(s);
    	DFS_CRetval dfsRet = new DFS_CRetval(false, limit);
        while(!dfsRet.found) {
        	dfsRet = DFS_C(initialStateId, 0, dfsRet.limit);
        }
        
        //find the actions needed
        //stateSequence.add(initialStateId);
        int totalCost = 0;
        long lastStateId = initialStateId;
        for(int i=stateSequence.size()-1; i>=0; i--) {
        	s.setState(lastStateId);
        	ArrayList<Action> actions = new ArrayList<Action>();
        	s.getActions(actions);
        	for(Action action: actions) {
        		int actionCost = s.getCost(action);
        		s.make(action);
        		if(s.getStateID()==stateSequence.get(i)) {
        			solution.add(action);
        			lastStateId = s.getStateID();  
        			totalCost += actionCost;
        			break;
        		}
        		else {
        			s.retract(action);
        		}
        	}
        }
        cost.value = totalCost;        
		return dfsRet.found;				
	}
	
    // Cost-bounded Depth-First Search
    private DFS_CRetval DFS_C(long stateId, int cost, int f_limit)
    {
    	/*
			DFS_C( State n, Cost g, Cost f_limit) { 
				// Explicitly keep track of g() cost. 
				if ( h( n ) == 0 ) return <true,  g>; 
				min_limit= INFINITY; 
				for ( each successor s of n) { 
					g_prime = g + cost( n, s ) 
					f = g_prime + h( s ); 
					if ( f<=f_limit) { 
						<found, next_limit> = DFS_C( s, g_prime, f_limit); 
						if ( found ) return <true, next_limit>; 
					} 
					else next_limit=f; 
					min_limit= min( next_limit, min_limit); 
				} 
				return <false, min_limit>; 
			} 
    	 */
    	
    	
    	state.setState(stateId);
    	//int h = heuristic.getHeuristic(state);
    	if(state.isGoal()) {
    		return new DFS_CRetval(true, cost);
    	}
    	int min_limit = Integer.MAX_VALUE;
	    m_nodesExpanded++;
	    ArrayList<Action> actions = new ArrayList<Action>();
	    state.getActions( actions );	    	    
	    for(Action action: actions) {
	    	int actionCost = state.getCost(action);    	    	
	    	state.make(action);
	    	long neighborStateId = state.getStateID();
	    	int g_prime = cost + actionCost;
	    	int f = g_prime + heuristic.getHeuristic(state);
	    	if(f<=f_limit) {
	    		DFS_CRetval retval = DFS_C(neighborStateId, g_prime, f_limit);
	    		if(retval.found) {
	    			stateSequence.add(neighborStateId);
	    			return retval;
	    		}
	    		else {
	    			min_limit = Math.min(retval.limit, min_limit);
	    		}
	    	}
	    	else {
	    		int next_limit = f;
	    		min_limit = Math.min(next_limit, min_limit);
	    	}
    		state.retract(action);
	    }    	    
    	return new DFS_CRetval(false, min_limit);
    }
	
    /*
	public int costFunction(int cost, State s) {
		return cost + heuristic.getHeuristic(s);
	}
	*/
	
	// Get number of nodes expanded.
	public long getNodesExpanded() {
		return m_nodesExpanded;
	}

	///////// Private ///////////
	private long m_nodesExpanded;
}
